//遍历二叉搜索树，若有值则返回地址
using namespace std;
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};



//递归法
TreeNode* traversal(TreeNode* cur,int val)
{
    if(cur->val==val) return cur;   //匹配
    if(!cur->right&&!cur->left&&cur->val!=val) return nullptr;  //叶子节点而且不匹配
    if(cur->val>val&&cur->left) return traversal(cur->left,val);    //大了，遍历左子树
    if(cur->val<val&&cur->right) return traversal(cur->right,val);  //小了，遍历右子树
    return nullptr;
}
TreeNode* searchBST(TreeNode* root, int val) {
    if(!root) return nullptr;
    return traversal(root,val);
}

//迭代法，只需走向左右节点即可，麻烦点用栈也可以
TreeNode* searchbst(TreeNode* root,int val){
    while(root){
        if(root->val==val) return root;


        if(root->val>val) root=root->left;
        else if(root->val<val) root=root->right;
        //一定要用else if 因为每次循环只走一步
    }
    return nullptr;
}